#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2019 crane <crane@gosun>
#
# Distributed under terms of the MIT license.


"""
https://www.lintcode.com/problem/reverse-pairs/description
"""

import time


class TrivalMerge:
    """
    普通版
    """
    def merge_sort(self, A):
        self.len = len(A)
        base  = list(A)             #
        extra = self.len * [0]       # 辅助/extra

        l = self.mergesort_rec(base, extra, 0, self.len)
        # print(base)

    def mergesort_rec(self, base, extra, b_idx, e_idx):
        # [b, e) 开闭区间
        if e_idx - b_idx == 1:
            return

        mid_idx = (b_idx + e_idx) // 2
        self.mergesort_rec(base, extra, b_idx, mid_idx)
        self.mergesort_rec(base, extra, mid_idx, e_idx)

        left_idx = b_idx
        right_idx = mid_idx
        extra_idx = b_idx

        while left_idx < mid_idx and right_idx < e_idx:
            if base[left_idx] <= base[right_idx]:
                hit = left_idx
                left_idx += 1
            else:
                hit = right_idx
                right_idx += 1
            extra[extra_idx] = base[hit]
            extra_idx += 1

        if left_idx == mid_idx:
            extra[extra_idx:e_idx] = base[right_idx:e_idx]
        else:
            extra[extra_idx:e_idx] = base[left_idx:mid_idx]

        # copy to base
        base[b_idx:e_idx] = extra[b_idx:e_idx]


class EnhanceMerge:
    """
    减少拷贝版(更优)
    """
    def merge_sort(self, A):
        self.len = len(A)
        base  = list(A)             #
        extra = self.len * [0]       # 辅助/extra

        up_down = self.mergesort_rec(base, extra, 0, self.len)
        # if up_down:
        #     print(extra)
        # else:
        #     print(base)

    def bubble_sort(self, base, b_idx, e_idx):
        # b_idx = 0
        # e_idx = len(base)

        for i in range(b_idx, e_idx):
            for j in range(e_idx-1, i, -1):
                if base[j-1] >= base[j]:
                    base[j-1], base[j] = base[j], base[j-1]
        # print('bubble ', base)
        return base

    def mergesort_rec(self, base, extra, b_idx, e_idx):
        # [b, e) 开闭区间
        if e_idx - b_idx < 9:
            # self.bubble_sort(base[b_idx:e_idx])
            self.bubble_sort(base, b_idx, e_idx)
            return False

        # if e_idx - b_idx == 1:
        #     return False

        mid_idx = (b_idx + e_idx) // 2
        up_down1 = self.mergesort_rec(base, extra, b_idx, mid_idx)
        up_down2 = self.mergesort_rec(base, extra, mid_idx, e_idx)

        left_idx = b_idx
        right_idx = mid_idx
        extra_idx = b_idx

        if up_down1 == up_down2 and up_down1 == True:
            base, extra = extra, base
        if up_down1 != up_down2:
            # 把颠倒的复原
            if up_down1:
                base[b_idx:mid_idx] = extra[b_idx:mid_idx]
            else:
                base[mid_idx:e_idx] = extra[mid_idx:e_idx]

            up_down1 = up_down2 = False

        while left_idx < mid_idx and right_idx < e_idx:
            if base[left_idx] <= base[right_idx]:
                hit = left_idx
                left_idx += 1
            else:
                hit = right_idx
                right_idx += 1
            extra[extra_idx] = base[hit]
            extra_idx += 1

        if left_idx == mid_idx:
            extra[extra_idx:e_idx] = base[right_idx:e_idx]
        else:
            extra[extra_idx:e_idx] = base[left_idx:mid_idx]

        # copy to base
        # base[b_idx:e_idx] = extra[b_idx:e_idx]

        # NOTE
        if up_down1 is True:
            assert up_down2 is True
            # print('hit ', b_idx, e_idx)

        return not up_down1

class BetterMerge:
    """
    普通版
    """
    def merge_sort(self, A):
        self.len = len(A)
        # base  = list(A)             #
        extra = list(A)

        l = self.mergesort_rec(A, extra, 0, self.len)
        # print(base)

    def bubble_sort(self, base, b_idx, e_idx):
        for i in range(b_idx, e_idx):
            for j in range(e_idx-1, i, -1):
                if base[j-1] >= base[j]:
                    base[j-1], base[j] = base[j], base[j-1]
        # print('bubble ', base)
        return base

    def mergesort_rec(self, base, extra, b_idx, e_idx):
        # [b, e) 开闭区间
        if e_idx - b_idx < 9:
            self.bubble_sort(base, b_idx, e_idx)
            return

        # if e_idx - b_idx == 1:
        #     return

        mid_idx = (b_idx + e_idx) // 2
        self.mergesort_rec(extra, base, b_idx, mid_idx)
        self.mergesort_rec(extra, base, mid_idx, e_idx)
        self.merge(extra, base, b_idx, mid_idx, e_idx)

    def merge(self, src, dst, b_idx, mid_idx, e_idx):
        left_idx = b_idx
        right_idx = mid_idx
        extra_idx = b_idx

        while left_idx < mid_idx and right_idx < e_idx:
            if src[left_idx] <= src[right_idx]:
                hit = left_idx
                left_idx += 1
            else:
                hit = right_idx
                right_idx += 1
            dst[extra_idx] = src[hit]
            extra_idx += 1

        if left_idx == mid_idx:
            dst[extra_idx:e_idx] = src[right_idx:e_idx]
        else:
            dst[extra_idx:e_idx] = src[left_idx:mid_idx]


def test():
    begin = time.time()

    # s = TrivalMerge()             # 每次拷贝版: 耗时27s
    # s = EnhanceMerge()          # 减少拷贝, 大约优化了7% 到10%性能. 1000w 25.04s
    s = BetterMerge()          # 减少拷贝, 大约优化了7% 到10%性能. 1000w 24.19s

    # lst = [2, 4, 1, 3, 5, -1, 8, 5, 6, 99, 101, 87]
    # s.merge_sort(lst)

    # lst = range(100, -1, -1)
    # s.merge_sort(lst)

    lst = list(range(58, -1, -1))
    s.merge_sort(lst)
    print(lst)

    # s.bubble_sort([4, 3, 2, 1])
    # s.bubble_sort([4, 3, 1, 2])
    # s.bubble_sort([1, 3, 4, 2])

    # for i in range(1, 100):
    i = 1000 * 10000
    # i = 1000 * 10
    lst = range(i, -1, -1)
    # s.merge_sort(lst)

    print("time spend ", time.time() - begin)

def main():
    print("start main")
    test()

if __name__ == "__main__":
    main()
